This invention relates to data compression. More specifically, the invention relates to a new cubic-spline interpolation (CSI) for both 1-D and 2-D signals to sub-sample signal and image compression data.
In most multimedia systems the amount of image data is so large that the use of image data compression is almost mandatory. Image data compression allows the image to be transmitted over the Internet in real time. Also it reduces the requirements for image storage. Presently both spatial and temporal data reduction techniques are available and continue to improve the performance of image data compression. The fundamental problem of image data compression is to increase the compression ratio and to reduce the computational complexity within an acceptable fidelity.
Interpolation is one of the more important functions that can be used in the process of estimating the intermediate values of a set of discrete sampling points. Interpolation is used extensively in image data compression to magnify or reduce images and to correct spatial distortions. For example, see R. G. Keys, xe2x80x9cCubic Convolution Interpolation for Digital Image Processing,xe2x80x9d IEEE Trans. on Acoustics, Speech, and Signal Processing, vol. ASSP-29, no.6, pp. 1153-1160, December 1981, [1], the contents of which are hereby expressly incorporated by reference. In general, the process of decreasing the data rate is called decimation and the process of increasing data samples is called interpolation as described in H. S. Hou, and H. C. Andrews, xe2x80x9cCubic Splines for Image Interpolation and Digital Filtering,xe2x80x9d IEEE Trans. on Acoustics, Speech, and Signal Processing, vol. ASSP-26, no.6, pp.508-517, December 1978, [2], the contents of which are hereby expressly incorporated by reference.
It is well known that several interpolation functions such as linear interpolation (see, W. K. Pratt, Digital Image Processing, second edition, John Wiley and Sons, Inc., New York, 1991, [3], the contents of which are hereby expressly incorporated by reference.) cubic-convolution interpolation (see [1], and [3]), cubic B-spline interpolation (described to C. de Boor, A Practical Guide to Splines. New York: Springer-Verlag, 1978, [4]; M. Unser, A. Aldroubi, and M. Eden, xe2x80x9cB-Spline Signal Processing: Part II-Efficient Design and Applications,xe2x80x9d IEEE Trans. on Signal Processing, vol.41, pp.834-848, February 1993, [5]; M. Unser, A. Aldroubi, and M. Eden, xe2x80x9cEnlargement or Reduction of Digital Images with Minimum Loss of Information,xe2x80x9d IEEE Trans. on Image Processing, vol.4, pp.247-258, March 1995, [6]; and [2]) can be used in the image data compression process.
The disadvantage of these interpolation schemes is that in general they are not designed to minimize the error between the original image and its reconstructed image. In 1981 Reed (I. S. Reed, Notes on Image Data Compression Using Linear Spline Interpolation, Department of Electrical Engineering, University of Southern California, Los Angeles, Calif., 90089-2565, U.S.A., November 1981 [7], the contents of which are hereby incorporated by reference) and in 1998 Reed and Yu (I. S. Reed and A. Yu, Optimal Spline Interpolation for Image Compression, U.S. Pat. No. 5,822,456, Oct. 13, 1998 [8], the contents of which are hereby incorporated by reference) developed a linear spline interpolation scheme for re-sampling the image data. This linear spline interpolation is based on the least-squares method with the linear interpolation function.
Using an extension of the ideas of Reed in [7,8], a modified linear spline interpolation algorithm, called the cubic-spline interpolation (CSI) algorithm, is developed in this invention for the sub-sampling of image data. (The linear spline interpolation explained in [8]and used by America On Line(trademark) (AOL) will be called the xe2x80x9cAOL algorithmxe2x80x9d in this document from hereon.)
It follows from [1]that the cubic-convolution interpolation, which is different from the B-spline interpolation, can be performed much more efficiently than that of the cubic B-spline interpolation method. In this invention, the new CSI scheme combines the least-squares method with a cubic-spline function developed by Keys [1]for the decimation process. Also the cubic-spline reconstruction is used in the interpolation process. Therefore, the CSI constitutes a new scheme that is quite different from both cubic B-spline interpolation [2,-6]and cubic-convolution interpolation [1,3].
The concept of the CSI for both 1-D and 2-D signals is describes and demonstrated in the following sections. In addition, it is shown by computer simulation that the CSI scheme obtains a better subjective quality for the reconstructed image than linear interpolation, cubic-convolution interpolation, cubic B-spline interpolation and linear spline interpolation. An important advantage of this new CSI scheme is that it can be computed by a use of the FFT technique. The complexity of the calculation of the CSI scheme is substantially less than other conventional means.
W. B. Pennebaker and J. L. Mitchell, JPEG Still Image Data Compression Standard, Van Nostrand Reinhold, New York, 1993, [9], the contents of which are hereby incorporated by reference, describes the JPEG still image data compression standard. It is well known that the JPEG (see [9]) algorithm is the international compression standard for still-images. The disadvantage of the conventional JPEG algorithm is that it causes visually disturbing blocking effects when high quantization parameter is used to obtain a high compression ratio. One embodiment of this invention includes a simpler and modified JPEG encoder-decoder to improve the JPEG standard with a high compression ratio and still maintain a good quality reconstructed image.
Recently, the authors in T. K. Truong, L. J. Wang, I. S. Reed, W. S. Hsieh, and T. C. Cheng xe2x80x9cImage data compression using cubic convolution spline interpolation,xe2x80x9d accepted for publication in IEEE Transactions on Image Processing[10], the contents of which are hereby incorporated by reference, proposed the modified JPEG encoder-decoder for xcfx84=2 that utilizes the CSI scheme with a compression ratio of 4 to 1 as a pre-processing stage of the JPEG encoder and the cubic-spline reconstruction with a ratio of 1 to 4 as a post-processing stage of the inverse JPEG decoder to achieve a high compression ratio.
In such a modified JPEG encoder the CSI scheme is the pre-processing stage of the JPEG encoder. It can be implemented by the use of the FFT algorithm. In addition, the output of the modified JPEG encoder represents the compressed data to be transmitted. It can be pre-computed and stored. In such a modified JPEG decoder, the cubic-spline reconstruction constitutes the post-processing stage of the JPEG decoder. This post-processing stage is different from the conventional post-processing algorithms that were proposed to reduce the blocking effects of block-based coding in B. Ramamurthi and A. Gersho, xe2x80x9cNonlinear space variant post-processing of block coded images,xe2x80x9d IEEE Trans. on Acoustics, Speech, Signal Processing, vol. ASSP-34, pp.1258-1267, 1986, [11], Y. Yang, N. Galatsanos, and A. Katsaggelos, xe2x80x9cProjection-based spatially adaptive reconstruction of block-transform compressed images,xe2x80x9d IEEE Trans. on Image Processing, vol.4, pp.896-908, July 1995 [12], the contents of which are hereby incorporated by reference.
The proposed post-processing stage is an interpolation process that uses the cubic-convolution interpolation. In [10], a computer simulation shows that the modified JPEG encoder-decoder for xcfx84=2 obtains a better subjective quality and an objective PSNR of the reconstructed image than the JPEG algorithm described in T. Lane, Independent JPEG Group""s free JPEG software, 1998, [13], the contents of which are hereby incorporated by reference; and [9]. Furthermore, the modified inverse JPEG decoder requires less computational time than the conventional JPEG decoder. But, the disadvantage of the modified JPEG encoder-decoder for xcfx84=2 is that the computational time required for the modified JPEG encoder is greater than the conventional JPEG encoder.
Thus, in one aspect, the present invention describes a fast method to compute the modified JPEG encoder. It is shown in this aspect of the invention that the speed of the new method for computing the modified JPEG encoder is approximately two times faster than that of the conventional JPEG encoder with still a good quality of reconstructed image.
The present invention describes a new cubic-spline interpolation (CSI) for both 1-D and 2-D signals to sub-sample signal and image compression data. This new interpolation scheme which is based on the least-squares method with a cubic-spline function can be implemented by the fast Fourier transform (FFT), and/or by a Winograd discrete Fourier transform (WDFT). The result is a simpler and faster interpolation design than can be obtained by conventional means. It is shown by computer simulation that such a new CSI yields the most accurate algorithms for smoothing. Linear interpolation, linear spline interpolation, cubic-convolution interpolation and cubic B-spline interpolation tend to be inferior in performance. In addition it is shown in this invention that the CSI scheme can be performed by a fast and efficient computation. The proposed method uses a simpler technique in the decimation process. It requires substantially fewer additions and multiplications than the original CSI algorithm.
In one aspect, the present invention is a method and system for defining a cubic-spline filter; correlating the filter with the signal to obtain a correlated signal; autocorrelating the filter to obtain autocorrelated filter coefficients; computing a transform of the correlated signal and the autocorrelated filter coefficients; dividing the transform of the correlated signal by the transform of the autocorrelated filter coefficients to obtain a transform of a compressed signal; and computing an inverse transform of the transform of the compressed signal to obtain the compressed signal. The signal, the filter, and the transforms may be one dimensional or two dimensional. Further, the transforms may be a fast Fourier transform (FFT) or a Winograd discrete Fourier transform (WDFT) with an overlap-save scheme. Also, a zonal filter may be defined to simplify the steps of correlating and autocorrelating.
Furthermore, a new type of overlap-save scheme can be utilized to solve the boundary-condition problems that occur between two neighboring sub-images in the actual image for higher compression ratios. It is also shown in this invention that a very efficient 9-point Winograd discrete Fourier transform (WDFT) can be used to replace the FFT needed to implement the CSI scheme image for higher compression ratio of 9 to 1. Finally, a fast new CSI algorithm is used along with the Joint Photographic Experts Group (JPEG) standard to design a modified JPEG encoder-decoder for image data compression. As a consequence, for the higher compression ratios the proposed modified JPEG encoder-decoder obtains a better quality of reconstructed image and also requires less computational time than both the conventional JPEG method and the America on Line (AOL) algorithm.